package org.yimon.tool.algo.meituan;

/**
 * @Author yimon.gao
 * @Description 美团进阶版-链表翻转
 * 对链表指定范围内子链表进行翻转，例如链表：2->3->6->1->8->0->9->null，翻转[2，5]部分，结果为：2->8->1->6->3->0->9->null
 * @Date 2024/10/16 10:39
 */
public class MeiTuan_ReverseList {

    public static void main(String[] args) {
        System.out.println(MeiTuan_ReverseList.reverseList(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 2, 4));
    }

    public static ListNode reverseList(ListNode head, int m, int n) {
        if (head == null || head.next == null || m >= n) {
            //当前链表为空或者只有一个节点或者范围不合法的情况无需反转直接返回
            return head;
        }
        ListNode first = head;//记录第一无需翻转的部分
        ListNode pre = null;//上一个节点
        for (int i = 0; i < m-1; i++) {
            pre = head;
            head = head.next;
        }
        ListNode second = head;//记录第二需要翻转的部分
        pre.next = null;//这样first就是完全的第一无需翻转的部分
        //对第二部分进行翻转
        ListNode tail = null;
        for (int i = 0; i < n-1; i++) {
            ListNode next = second.next;
            second.next = tail;
            tail = second;
            second = next;
        }
        ListNode three = second;//第三无需翻转的部分
        second = tail;
        //拼接三个部分：first + second + three
        ListNode result = first;
        while (first.next != null) {
            first = first.next;
        }
        first.next = second;
        while (first.next != null) {
            first = first.next;
        }
        first.next =  three;


        return result;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
